package l07_dynamic_planning;

/**
 * @author wangxiyue@cyou-inc.com
 * @date 2019-08-21
 * @since 1.0.0
 */
public class LeetCode_72 {
    /*
     * @lc app=leetcode.cn id=72 lang=java
     *
     * [72] 编辑距离
     *
     * https://leetcode-cn.com/problems/edit-distance/description/
     *
     * algorithms
     * Hard (53.74%)
     * Likes:    294
     * Dislikes: 0
     * Total Accepted:    11.4K
     * Total Submissions: 21.2K
     * Testcase Example:  '"horse"\n"ros"'
     *
     * 给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数 。
     *
     * 你可以对一个单词进行如下三种操作：
     *
     *
     * 插入一个字符
     * 删除一个字符
     * 替换一个字符
     *
     *
     * 示例 1:
     *
     * 输入: word1 = "horse", word2 = "ros"
     * 输出: 3
     * 解释:
     * horse -> rorse (将 'h' 替换为 'r')
     * rorse -> rose (删除 'r')
     * rose -> ros (删除 'e')
     *
     *
     * 示例 2:
     *
     * 输入: word1 = "intention", word2 = "execution"
     * 输出: 5
     * 解释:
     * intention -> inention (删除 't')
     * inention -> enention (将 'i' 替换为 'e')
     * enention -> exention (将 'n' 替换为 'x')
     * exention -> exection (将 'n' 替换为 'c')
     * exection -> execution (插入 'u')
     *
     *
     */
    static class Solution {
        public int minDistance(String word1, String word2) {

            char[] chars1 = word1.toCharArray();
            char[] chars2 = word2.toCharArray();

            if (chars1.length == 0 || chars2.length == 0) {
                return Integer.max(chars1.length, chars2.length);
            }

            int dp[][] = new int[chars1.length + 1][chars2.length + 1];
            for (int i = 0; i < chars1.length + 1; i++) {
                dp[i][0] = i;
            }

            for (int j = 0; j < chars2.length + 1; j++) {
                dp[0][j] = j;
            }


            int i, j;
            for (i = 1; i <= chars1.length; i++) {
                for (j = 1; j <= chars2.length; j++) {
                    int temp = 0;
                    if (chars1[i - 1] != chars2[j - 1]) {
                        temp = 1;
                    }
                    dp[i][j] = Integer.min(Integer.min(dp[i - 1][j] + 1,
                            dp[i][j - 1] + 1), dp[i - 1][j - 1] + temp);
//                    System.out.println("dp[" + (i) + "][" + (j) + "]" + dp[i][j]);
                }
            }
            return dp[chars1.length][chars2.length];
        }
    }

    public static void main(String[] args) {
//        System.out.println(new Solution().minDistance("ros", "horse")); //3
//        System.out.println(new Solution().minDistance("execution", "intention")); //5
//        System.out.println( new Solution().minDistance("", "")); // 0
//        System.out.println(new Solution().minDistance("a", "ab"));  //2
//        System.out.println(new Solution().minDistance("sea", "ate")); //3
//        System.out.println(new Solution().minDistance("sea", "sea")); //0
//        System.out.println(new Solution().minDistance("sea", "eat")); //2
        System.out.println(new Solution()
                .minDistance("pneumonoultramicroscopicsilicovolcanoconiosis",
                        "ultramicroscopically")); //27

    }
}







